//----------------------------------------------------------------------中国剩余定理


/*
 * input: 
 * 	t=a mod b ,
 * 	t=c mod d ;
 * output:
 * 	t=x mod y ;
 *
 * 	ret:1--OK,
 * 	0--NO ANS
*/

int CRT(LL a,LL b,LL c,LL d,LL *x,LL *y)
{
	LL gcd;
	ext_gcd(b,d,&gcd,x,y);
	if((a-c)%gcd!=0)return 0;
	*y=b/gcd*d;
	d/=gcd;
	*x=*x%d*(c-a)/gcd%d;
	*x=((b**x+a)%*y+*y)%*y;
	return 1;
}



/* 线性同余方程
 * input:
 * 	(a,b,c)   |    ax=b mod c
 *
 * output:
 * 	(ret,mo)  |    x=ret mod mo
 *
 * 	return:
 * 		1:OK
 * 		0:NO ANS
 *
 * */
int modlinear(LL a,LL b,LL c,LL *ret,LL *mo)//ax=b(mod c)
{
	LL d;LL x,y;
    	ext_gcd(a,c,&d,&x,&y);
    	if(b%d)return 0;
	c/=d;b/=d;
    	x=(x%c+c)%c;
    	*mo=c;
    	*ret=(x*b%c);
    	return 1;
}
